#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
	vector<vector<string>> solveNQueens(int n) {
		layer.resize(n, -1);

		backtrack(0);
		return res;
	}

private:
	int columns = 0, diagonals1 = 0, diagonals2 = 0;
	vector<char> layer; vector<vector<string>> res;

	void backtrack(int row) {
		if (row == layer.size())
			res.emplace_back(geneteBoard());
		else {
			for (int col = 0, len = layer.capacity(); col < len; col++) {
				int bit = 1 << col;
				if (bit & columns || (bit << row) & diagonals1 || (bit << 9 - row) & diagonals2) continue;
				columns |= bit; diagonals1 |= bit << row; diagonals2 |= bit << 9 - row;
				layer[row] = col;
				backtrack(row + 1);
				columns ^= bit; diagonals1 ^= bit << row; diagonals2 ^= bit << 9 - row;
			}
		}
	}

	vector<string>&& geneteBoard() {
		vector<string> board;
		int n = layer.capacity();
		for (char idx : layer)
			board.emplace_back(n, '.')[idx] = 'Q';
		return move(board);
	}
};

int main()
{
	Solution solution;
	return 0;
}
